package com.lwl.Algorithmic_data_structure.class20暴力递归2动态规划;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author lwl
 * @Description 给你一个咖啡机数组machines[]用于制作咖啡, 每个元素对应制作一杯咖啡的时间, N个人, 一台洗杯子机器, a秒内洗干净一个杯子, 不洗的话b秒内挥发干净
 * 请你求出所有人喝完并且杯子都干净的时间 (杯子是无限量的,喝咖啡不计时间,即制作完和洗杯子可以是同一时间)
 * <p>
 * 这需要将问题拆分, 1. 所有人喝完咖啡的时间 2. 所有杯子洗干净的时间
 * @date 2023/6/11 12:09
 */
public class Code03Coffee {

    public static void main(String[] args) {
        
    }
    
    static class Machine {
        /**
         * 机器空闲的起始点
         */
        int freeStartMoment;

        /**
         * 制作一杯咖啡所需时间
         */
        int makeCoffeeTime;

        public Machine(int freeStartMoment, int makeCoffeeTime) {
            this.freeStartMoment = freeStartMoment;
            this.makeCoffeeTime = makeCoffeeTime;
        }
    }

    static private int washCup;

    static private int dryCup;

    static public int coffee(int[] machines, int n, int a, int b) {
        washCup = a;
        dryCup = b;

        // 1. 所有人喝完的最短时间,这里取决于咖啡机制作的时间,建立一个小根堆,每次从堆顶取出元素表示可用
        PriorityQueue<Machine> minHeap = new PriorityQueue<>(machines.length, new Comparator<Machine>() {
            // 返回负数 第一个参数排前面
            @Override
            public int compare(Machine m1, Machine m2) {
                return (m1.freeStartMoment + m1.makeCoffeeTime) - (m2.freeStartMoment + m2.makeCoffeeTime);
            }
        });
        for (int j : machines) {
            minHeap.add(new Machine(0, j));
        }
        // 每个人喝完的时间点,因为喝咖啡不消耗时间,所以开始的时间就是结束的时间
        int[] drinks = new int[n];
        for (int i = 0; i < n; i++) {
            Machine machine = minHeap.poll();
            machine.freeStartMoment = machine.freeStartMoment + machine.makeCoffeeTime;
            drinks[i] = machine.freeStartMoment;
            minHeap.add(machine);
        }
        // 现在对drinks的判断就是哪一杯要洗,哪一杯要风干了
        return process(drinks, 0, 0);
    }

    private static int process1(int[] drinks) {
        // int index, int canWashTime
        // dp数组数组的两维,这里canWashTime需要独立计算出最大值
        int maxCanWashTime = 0;
        for (int i = 0; i < drinks.length; i++) {
            maxCanWashTime = Math.max(maxCanWashTime, drinks[i]) + washCup;
        }
        // 下标是可以到n 和 maxCanWashTime的
        int N = drinks.length;
        int[][] dp = new int[N + 1][maxCanWashTime + 1];

        for (int i = 0; i <= maxCanWashTime; i++) {
            dp[N][i] = 0;
        }

        for (int index = N - 1; index >= 0; index--) {
            for (int canWashTime = 0; canWashTime <= maxCanWashTime; canWashTime++) {
                // 洗
                // 洗干净自身需要的时间
                int washSelf = Math.max(canWashTime, drinks[index]) + washCup;
                if (washSelf > maxCanWashTime) {
                    continue;
                }
                // int washLeft = process(drinks, index + 1, washSelf);
                int washLeft = dp[index + 1][washSelf];

                // 风干
                // 风干自身需要的时间
                int drySelf = drinks[index] + dryCup;
                // int dryLeft = process(drinks, index + 1, canWashTime);
                int dryLeft = dp[index + 1][canWashTime];

                int chooseWash = Math.max(washSelf, washLeft);
                int chooseDry = Math.max(drySelf, dryLeft);

                dp[index][canWashTime] = Math.min(chooseWash, chooseDry);
            }
        }

        return dp[0][0];
    }

    private static int process(int[] drinks, int index, int canWashTime) {

        if (index == drinks.length) {
            return 0;
        }
        // 选择 洗还是风干

        // 洗
        // 洗干净自身需要的时间
        int washSelf = Math.max(canWashTime, drinks[index]) + washCup;
        int washLeft = process(drinks, index + 1, washSelf);
        // 风干
        // 风干自身需要的时间
        int drySelf = drinks[index] + dryCup;
        int dryLeft = process(drinks, index + 1, canWashTime);

        int chooseWash = Math.max(washSelf, washLeft);
        int chooseDry = Math.max(drySelf, dryLeft);

        return Math.min(chooseWash, chooseDry);
    }
}
